package cm.commom;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class TreeNode {
	public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }

    private static boolean isEmptyTree(TreeNode root){
        return root == null;
    }

    @Override
    public String toString() {
    	return prePrint(this);
    }

    // 前序
	public static String prePrint(TreeNode treeNode) {
		if (treeNode!=null) {
			StringBuilder result = new StringBuilder();
			result.append(treeNode.val);

            String strLeft = prePrint(treeNode.left);
            if (!"".equals(strLeft)){
                result.append(" ").append(prePrint(treeNode.left));
            }

            String strRight = prePrint(treeNode.right);
            if (!"".equals(strRight)){
                result.append(" ").append(prePrint(treeNode.right));
            }

			return new String(result);
		}
		return "";
	}

	// 层序遍历
    public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>(100);

        // queue的值不能为null
        if (root!=null){
            queue.add(root);
        }

        TreeNode node;
        while (!queue.isEmpty()){
            node = queue.remove();
            list.add(node.val);
            if (node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
        }
        return list;
    }

    public static TreeNode buildDemoTree(){
        TreeNode root = new TreeNode(8);

        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(10);
        root.left = node1;
        root.right = node2;

        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(7);
        node1.left = node3;
        node1.right = node4;


        TreeNode node5 = new TreeNode(9);
        TreeNode node6 = new TreeNode(11);
        node2.left = node5;
        node2.right = node6;

        return  root;
    }

    public static String serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }

        Queue<TreeNode> queue = new ArrayDeque<>(100);
        StringBuilder builder = new StringBuilder();

        // queue的值不能为null

        queue.add(root);
        builder.append(root.val);

        TreeNode node;
        while (!queue.isEmpty()) {
            node = queue.remove();

            // 持久化
            if (node.left != null) {
                builder.append("!").append(node.left.val);
                queue.add(node.left);
            }else {
                builder.append("!#");
            }

            if (node.right != null) {
                builder.append("!").append(node.right.val);
                queue.add(node.right);
            }else {
                builder.append("!#");
            }
        }
        return new String(builder);
    }

    /**
     * 由层序遍历的序列化字符串得到原树
     *
     * @param str "!" : 分隔树节点； "#" : 代表空节点
     * @return
     */
    public static TreeNode deserialize(String str) {
        if (str==null || str.length()==0){
            return null;
        }

        Queue<TreeNode> queue = new ArrayDeque<>(100);
        String[] strings = str.split("!");
        TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
        queue.add(root);

        TreeNode node;
        int index = 1;
        while (!queue.isEmpty() && index<strings.length){
            node = queue.remove();

            if (!"#".equals(strings[index])){
                TreeNode leftNode = new TreeNode(Integer.parseInt(strings[index++]));
                node.left = leftNode;
                queue.add(leftNode);
            }else {
                index++;
            }

            if (!"#".equals(strings[index])){
                TreeNode rightNode = new TreeNode(Integer.parseInt(strings[index++]));
                node.right = rightNode;
                queue.add(rightNode);
            }else {
                index++;
            }
        }
        return root;
    }
    
    
}
